package pers.sloera.leetcode.editor.cn;


/**
 * 给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i +
 * 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：arr = [3,1,3,6]
 * 输出：false
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：arr = [2,1,2,6]
 * 输出：false
 * <p>
 * <p>
 * 示例 3：
 * <p>
 * <p>
 * 输入：arr = [4,-2,2,-4]
 * 输出：true
 * 解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
 * <p>
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * <p>
 * 0 <= arr.length <= 3 * 10⁴
 * arr.length 是偶数
 * -10⁵ <= arr[i] <= 10⁵
 * <p>
 * Related Topics 贪心 数组 哈希表 排序 👍 145 👎 0
 */

//leetcode submit region begin(Prohibit modification and deletion)

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Optional;
import java.util.stream.IntStream;

// class Solution {
class Solution954 {
    //     public static void main(String[] args) {
    //       Solution954 solution954 = new Solution954();
    //       System.out.println(solution954.canReorderDoubled(new int[]{3,1,3,6}));
    //       // System.out.println(solution954.canReorderDoubled(new int[]{2,1,2,6}));
    //       // System.out.println(solution954.canReorderDoubled(new int[]{4,-2,2,-4}));
    //       // System.out.println(solution954.canReorderDoubled((int[]) null));
    //     }

    public boolean canReorderDoubledList(int[] arr) {
        // 需要频繁增删，所以使用linkedList，使用arrayList会造成超时
        LinkedList<Integer> sourceList = new LinkedList<>();
        IntStream.of(arr).boxed().sorted().forEach(sourceList::add);
        // String s = FileUtil.readString("/home/data/git/gitee/java/leetcode/src/main/java/pers/sloera/leetcode/editor/cn/954.txt", StandardCharsets.UTF_8);
        // Arrays.stream(s.split(",")).map(Integer::valueOf).sorted().forEach(sourceList::add);
        return canReorderDoubled(sourceList);
    }

    /**
     * 判断list中的元素是否是2倍数对。入参已排序
     *
     * @param source 入参，需已升序排列
     * @return boolean true：是2倍数对
     * @date 2022/4/1
     */
    @SuppressWarnings("unchecked")
    private boolean canReorderDoubled(LinkedList<Integer> source) {
        if (source.size() > 0) {
            // 取第一个数
            Integer left = source.get(0);
            source.remove(left);
            // 负数，相除
            Integer right;
            if (left < 0) {
                // 得整除
                if (left % 2 != 0) {
                    return false;
                }
                right = left / 2;
            } else {
                right = left * 2;
            }
            if (source.contains(right)) {
                source.remove(right);
                // 重复的一次性都排除
                while (source.contains(left)) {
                    if (source.contains(right)) {
                        source.remove(left);
                        source.remove(right);
                    } else {
                        return false;
                    }
                }
                return canReorderDoubled(source);
            }
            return false;
        }
        return true;
    }

    public boolean canReorderDoubled(int[] arr) {
        // 需要频繁增删，所以使用linkedList，使用arrayList会造成超时
        HashMap<Integer, Integer> cacheMap = new HashMap<>();
        int zeroNum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                cacheMap.put(arr[i], cacheMap.getOrDefault(arr[i], 0) + 1);
            } else {
                zeroNum++;
            }
        }
        if (zeroNum % 2 != 0) {
            return false;
        }
        // 找到不符合的数
        Optional<Integer> first = cacheMap.keySet().stream().sorted().filter(x -> {
            Integer left = cacheMap.get(x);
            if (left.equals(0)) {
                return false;
            }
            // 负数，相除
            int rightIndex;
            if (x < 0) {
                // 得整除
                if (x % 2 != 0) {
                    return true;
                }
                rightIndex = x / 2;
            } else {
                rightIndex = x * 2;
            }
            // 不包含，也说明不符合
            if (!cacheMap.containsKey(rightIndex)) {
                return true;
            }
            Integer right = cacheMap.get(rightIndex);
            if (left > right) {
                return true;
            }
            cacheMap.put(x, 0);
            cacheMap.put(rightIndex, right - left);
            return false;
        }).findFirst();
        if (first.isPresent()) {
            return false;
        } else {
            return true;
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)
